package org.example.graph_theory;

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;

public class Largest_artificial_island {
    public static int land = 0;
    public static int maxLand = 0;
    public static HashMap<Integer, Integer> map = new HashMap<>();

    public static void main(String[] args) {
        //最大人工岛

        //给你一个大小为 n x n 二进制矩阵 grid 。最多 只能将一格 0 变成 1 。
        //返回执行此操作后，grid 中最大的岛屿面积是多少？
        //岛屿 由一组上、下、左、右四个方向相连的 1 形成。
        int[][] grid = {{0, 1}, {1, 0}};
//        int[][] grid = {
//                {1, 0, 1},
//                {0, 0, 0},
//                {0, 1, 1}
//        };

        int i = largestIsland(grid);
        System.out.println(i);

    }


    public static int largestIsland(int[][] grid) {
        int[][] visited = new int[grid.length][grid[0].length];
        trave2(grid, visited);
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == 0) {
                    HashSet<Integer> hashSet = new HashSet<>();
                    if (i-1>=0) hashSet.add(visited[i - 1][j]);
                    if (i+1< grid.length) hashSet.add(visited[i + 1][j]);
                    if (j-1>=0) hashSet.add(visited[i][j - 1]);
                    if (j+1<grid[i].length) hashSet.add(visited[i][j + 1]);
                    for (Integer index : hashSet) {
                        land += map.get(index);
                    }
                    maxLand = Math.max(maxLand,land+1);
                    land = 0;
                }
            }
        }

        return maxLand;
    }

    private static void trave2(int[][] island, int[][] visited) {
        int index = 1;
        map.put(0, 0);
        for (int i = 0; i < island.length; i++) {
            for (int j = 0; j < island[i].length; j++) {
                if (island[i][j] == 1 && visited[i][j] == 0) {
                    dfs2(island, visited, i, j, index);
                    map.put(index, land);
                    maxLand = Math.max(maxLand,land);
                    land = 0;
                    index++;
                }
            }
        }
    }

    public static void dfs2(int[][] island, int[][] visited, int i, int j, int index) {
        if (i < 0 || i >= island.length || j < 0 || j >= island[i].length || visited[i][j] != 0 || island[i][j] == 0)
            return;
        visited[i][j] = index;
        land++;
        dfs2(island, visited,i - 1, j,index);
        dfs2(island, visited,i, j - 1,index);
        dfs2(island,visited, i + 1, j,index);
        dfs2(island, visited,i, j + 1,index);
    }

    //简化暴力，仍热超时
    public static int largestIsland3(int[][] grid) {
        int[][] island = new int[grid.length][grid[0].length];
        fillarry(island, grid);
        trave(island);
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == 0) {
                    fillarry(island, grid);
                    island[i][j] = 1;
                    dfs(island, i, j);
                    maxLand = Math.max(maxLand, land);
                    land = 0;
                }
            }
        }

        return maxLand;
    }


    //暴力dfs，超时
    public static int largestIsland2(int[][] grid) {
        boolean flag = false;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == 0) {
                    flag = true;
                    int[][] island = new int[grid.length][grid[0].length];
                    fillarry(island, grid);
                    island[i][j] = 1;
                    trave(island);
                }
            }
        }
        if (!flag) {
            trave(grid);
        }

        return maxLand;
    }

    public static void trave(int[][] island) {
        for (int i = 0; i < island.length; i++) {
            for (int j = 0; j < island[i].length; j++) {
                if (island[i][j] == 1) {
                    dfs(island, i, j);
                    maxLand = Math.max(maxLand, land);
                    land = 0;
                }
            }
        }
    }

    public static void dfs(int[][] island, int i, int j) {
        if (i < 0 || i >= island.length || j < 0 || j >= island[i].length || island[i][j] == 0) return;
        island[i][j] = 0;
        land++;
        dfs(island, i - 1, j);
        dfs(island, i + 1, j);
        dfs(island, i, j - 1);
        dfs(island, i, j + 1);
    }

    public static void fillarry(int[][] island, int[][] grid) {
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                island[i][j] = grid[i][j];
            }
        }
    }
}
